package prepare.huawei;

import java.util.*;

/**
 * description: <a href="https://www.nowcoder.com/practice/97ba57c35e9f4749826dc3befaeae109?tpId=37&rp=1&ru=%2Fexam%2Foj%2Fta&qru=%2Fexam%2Foj%2Fta&sourceUrl=%2Fexam%2Foj%2Fta%3FtpId%3D37&difficulty=&judgeStatus=&tags=&title=&gioEnter=menu">火车进站</a>
 *
 * @author <a href="zhaoyingling12@163.com">simon zhao</a>
 * @since 2023/3/29
 */
public class TrainEntersStation {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Integer n = Integer.parseInt(in.nextLine());
        String[] ss = in.nextLine().split(" ");
        System.out.println("ss length = " + ss.length);
        Deque<String> stack = new LinkedList();
        List<String> res = new ArrayList();
        hepler(stack, res, ss, 0, "", 0);
        Collections.sort(res);
        for (String str : res) {
            System.out.println(str);
        }
    }

    /**
     *
     * @param stack
     * @param res
     * @param ss
     * @param index 取 ss 的 index 位置的元素
     * @param str 字符串
     * @param n 记录了拼接了几个数字
     */
    private static void hepler(Deque<String> stack, List<String> res, String[] ss, int index, String str, int n) {

        if (n == ss.length) {
            // 添加到 res
            res.add(str);
            return;
        }

        if (!stack.isEmpty()) {
            String s = stack.removeLast();
            printStack(stack);
            if (stack.size() > ss.length) {
                System.out.println("index = " + index);
            }
            hepler(stack, res, ss, index, str + s + " ", n + 1);
            stack.addLast(s);
        }

        if (index < ss.length) {
            stack.addLast(ss[index]);
            hepler(stack, res, ss, index + 1, str, n);
            // 思考 为什么这里也需要 remove
            stack.removeLast();
        }

    }

    private  static void printStack(Deque<String> stack) {
        List<String> list = new ArrayList<>(stack);
        StringBuilder builder = new StringBuilder();
        for (int i = list.size() - 1; i >= 0; i--) {
            builder.append(list.get(i)).append(" ");
        }
        System.out.println(builder);
    }
}
